#include"Sort.h"

//void PrintArray(int* a, int n)
//{
//	for (int i = 0; i < n; i++)
//	{
//		printf("%d ",a[i]);
//	}
//	printf("\n");
//}
//void InsertSort(int* a, int n)
//{
//	for (int i = 0; i < n - 1; i++)
//	{
//		int end = i;
//		int tmp = a[end + 1];
//		while (end >= 0)
//		{
//			if (tmp < a[end])
//			{
//				a[end + 1] = a[end];
//				--end;
//			}
//			else
//			{
//				break;
//			}
//			a[end + 1] = tmp;
//		}
//	}
//}
//void Swap(int* p1, int* p2)
//{
//	int tmp = *p1;
//	*p1 = *p2;
//	*p2 = tmp;
//}
//void BubbleSort(int* a, int n)
//{
//	for (int j = 0; j < n; j++)
//	{
//		for (int i = 0; i < n - 1; i++)
//		{
//			if (a[i + 1] < a[i])
//			{
//				Swap(&a[i + 1], &a[i]);
//			}
//		}
//	}
//}
//void SelectSort(int* a, int n)
//{
//	int begin = 0;
//	int end = n - 1;
//	while (begin < end)
//	{
//		int mini = begin;
//		int maxi = begin;
//		for (int i = begin+1; i <= end; i++)
//		{
//			if (a[i] < a[mini])
//			{
//				mini = i;
//			}
//			if (a[i] > a[maxi])
//			{
//				maxi = i;
//			}
//		}
//		Swap(&a[begin], &a[mini]);
//		if (maxi == begin)
//		{
//			maxi = mini;
//		}
//		Swap(&a[end], &a[maxi]);
//		++begin;
//		--end;
//	}
//}

//希尔排序1
//void ShellSort(int* a, int n)
//{
//	int gap = 3;
//	while (gap > 1)
//	{
//		gap = gap / 3 + 1;
//		for (int j = 0; j < gap; j++)
//		{
//			for (int i = j; i < n - gap; i += gap)
//			{
//				int end = i;
//				int tmp = a[end + gap];
//				while (end >= 0)
//				{
//					if (tmp < a[end])
//					{
//						a[end + gap] = a[end];
//						end -= gap;
//					}
//					else
//					{
//						break;
//					}
//					a[end + gap] = tmp;
//				}
//			}
//		}
//	}
//}
//希尔排序2
//void ShellSort(int* a, int n)
//{
//	int gap = n;
//	while (gap > 1)
//	{
//		gap = gap / 3 + 1;
//
//		for (int i = 0; i < n - gap; i++)
//		{
//			int end = gap;
//			int tmp = a[end + gap];
//			while (end >= 0)
//			{
//				if (tmp < a[end])
//				{
//					a[end + gap] = a[end];
//					end -= gap;
//				}
//				else
//				{
//					break;
//				}
//				a[end + gap] = tmp;
//			}
//		}
//	}
//}

//普通版快速排序
//void QuickSort(int* a, int begin, int end)
//{
//	if (begin >= end)
//		return;
//	int left = begin;
//	int right = end;
//	int keyi = begin;
//	while (left < right)
//	{
//		while (left < right && a[right] >= a[keyi])
//		{
//			--right;
//		}
//		while (left<right && a[left]<=a[keyi])
//		{
//			++left;
//		}
//		Swap(&a[left], &a[right]);
//	}
//	Swap(&a[left], &a[keyi]);
//	keyi = left;
//	//区间
//	//[begin,keyi-1] keyi [keyi+1,end]
//	QuickSort(a, begin, keyi - 1);
//	QuickSort(a, keyi + 1, end);
//}

//快速排序---三数取中
//int GetMidi(int* a, int begin, int end)
//{
//	int midi = (begin + end) / 2;
//	//begin		midi	end ---这三个数中取中间值 
//	if (a[begin] > a[midi])
//	{
//		if (a[midi] > a[end])
//			return midi;
//		else if (a[end] > a[begin])
//			return begin;
//		else
//			return end;
//	}
//	else//a[begin]<a[midi]
//	{
//		if (a[midi] < a[end])
//			return midi;
//		else if (a[begin] > a[end])
//			return begin;
//		else
//			return end;
//	}
//}
//void QuickSort(int* a, int begin, int end)
//{
//	int midi = GetMidi(a, begin, end);
//	Swap(&a[begin], &a[midi]);
//	int left = begin;
//	int right = end;
//	int keyi = begin;
//	while (left < right)
//	{
//		while (left < right && a[right] >= a[keyi])
//		{
//			--right;
//		}
//		while (left < right && a[left] <= a[keyi])
//		{
//			++left;
//		}
//		Swap(&a[left], &a[right]);
//	}
//	Swap(&a[left], &a[keyi]);
//	keyi = left;
//	//区间
//	//[begin,keyi-1] keyi [keyi+1,end]
//	PartSort1(a, begin, keyi - 1);
//	PartSort1(a, keyi + 1, end);
//}
//
//int PartSort1(int* a, int begin, int end)
//{
//	int midi = GetMidi(a, begin, end);
//	Swap(&a[midi], &a[begin]);
//	int left = begin, right = end;
//	int keyi = begin;
//	while (left < right)
//	{
//		// 右边找小
//		while (left < right && a[right] >= a[keyi])
//		{
//			--right;
//		}
//		// 左边找大
//		while (left < right && a[left] <= a[keyi])
//		{
//			++left;
//		}
//		Swap(&a[left], &a[right]);
//	}
//	Swap(&a[left], &a[keyi]);
//	return left;
//}
//挖坑法
//int PartSort2(int* a, int begin, int end)
//{
//	int midi = GetMidi(a, begin, end);
//	Swap(&a[midi], &a[begin]);
//	int keyi = a[begin];
//	int hole = begin;
//	while (begin < end)
//	{
//		//右边找小，填到左边的坑
//		while (begin < end && a[end] >= keyi)
//		{
//			--end;
//		}
//		a[hole] = a[end];
//		hole = end;
//		//左边找到，填到右边的坑
//		while (begin < end && a[begin] <= keyi)
//		{
//			++begin;
//		}
//		a[hole] = a[begin];
//		hole = begin;
//	}
//	a[hole] = keyi;
//	return keyi;
//}
//指针法
//int PartSort3(int* a, int begin, int end)
//{
//	int midi = GetMidi(a, begin, end);
//	Swap(&a[begin], &a[midi]);
//	int prev = begin;
//	int cur = prev + 1;
//	int keyi = begin;
//	while (cur <= end)
//	{
//		if (a[cur] < a[keyi] && ++prev != cur)
//		{
//			Swap(&a[prev], &a[cur]);
//		}
//		++cur;
//	}
//	Swap(&a[keyi], &a[prev]);
//	keyi = prev;
//	return prev;
//}
//void QuickSort(int* a, int begin, int end)
//{
//	if (begin >= end)
//		return;
//
//	int keyi = PartSort3(a, begin, end);
//	QuickSort(a, begin, keyi - 1);
//	QuickSort(a, keyi + 1, end);
//}

//非递归实现快速排序
//void QuickSortNonR(int* a, int begin, int end)
//{
//	ST s;
//	STInit(&s);
//	STPush(&s, end);
//	STPush(&s, begin);
//
//	while (!STEmpty(&s))
//	{
//		int left = STTop(&s);
//		STPop(&s);
//		int right = STTop(&s);
//		STPop(&s);
//
//		int keyi = PartSort3(a, left, right);
//		// [left, keyi-1] keyi [keyi+1, right]
//		if (left < keyi - 1)
//		{
//			STPush(&s, keyi - 1);
//			STPush(&s, left);
//		}
//
//		if (keyi + 1 < right)
//		{
//			STPush(&s, right);
//			STPush(&s, keyi + 1);
//		}
//	}
//	STDestroy(&s);
//}

//void _MergeSort(int* a, int begin, int end, int* tmp)
//{
//	if (begin >= end)
//		return;
//	int mid = (begin + end) / 2;
//	_MergeSort(a, begin, mid, tmp);
//	_MergeSort(a, mid + 1, end, tmp);
//
//	//[begin,mid] [mid+1,end]归并
//	int begin1 = begin, end1 = mid;
//	int begin2 = mid + 1, end2 = end;
//	int i = begin;
//	while (begin1 <= end1 && begin2 <= end2)
//	{
//		if (a[begin1] < a[begin2])
//		{
//			tmp[i++] = a[begin1++];
//		}
//		else
//		{
//			tmp[i++] = a[begin2++];
//		}
//	}
//	while (begin1 <= end1)
//	{
//		tmp[i++] = a[begin1++];
//	}
//	while (begin2 <= end2)
//	{
//		tmp[i++] = a[begin2++];
//	}
//	memcpy(a + begin, tmp + begin, sizeof(int) * (end - begin+1));
//}
////归并排序
//void MergeSort(int* a, int n)
//{
//	int* tmp = (int*)malloc(sizeof(int) * n);
//	if (tmp == NULL)
//	{
//		printf("malloc fail");
//		return;
//	}
//	_MergeSort(a, 0, n - 1, tmp);
//
//	free(tmp);
//}

/////////////////////////////////////////////////////////////////////////////
void PrintArray(int* a, int n)
{
	for (int i = 0; i < n; i++)
	{
		printf("%d ", a[i]);
	}
	printf("\n");
}

//冒泡排序
Swap(int* p1, int* p2)
{
	int tmp = *p1;
	*p1 = *p2;
	*p2 = tmp;
}
void BubbleSort(int* a, int n)
{
	for (int j = 0; j < n; j++)
	{
		for (int i = 0; i < n - j-1; i++)
		{
			if (a[i + 1] < a[i])
			{
				Swap(&a[i + 1], &a[i]);
			}
		}
	}
}
void InsertSort(int* a, int n)
{
	for (int i = 0; i < n-1; i++)
	{
		int end = i;
		int tmp = a[end + 1];
		while (end >= 0)
		{
			if (tmp < a[end])
			{
				a[end + 1] = a[end];
				--end;
			}
			else
			{
				break;
			}
		}
		a[end + 1] = tmp;
	}
}

void SelectSort(int* a, int n)
{
	//记录第一个和最后一个下标
	int begin = 0;
	int end = n - 1;
	while (begin < end)
	{
		//保存最大值，最小值下标
		int mini = begin;
		int maxi = begin;
		//找出最大值和最小值的下标
		for (int i = begin; i <= end; i++)
		{
			//找到最小值，将mini最小值下标更新为i位置
			if (a[i] < a[mini])
			{
				mini = i;
			}
			//找到最大值，将maxi最大值下标更新为i位置
			if (a[i] > a[maxi])
			{
				maxi = i;
			}
		}
		//此时最小值为序列开头处
		Swap(&a[mini], &a[begin]);
		//考虑到万一最大值在begin位置被mini换走，所以增加判断
		if (begin == maxi)
		{
			maxi = mini;
		}
		//此时最大值在序列末尾处
		Swap(&a[maxi], &a[end]);
		//begin往前后，不断更新
		++begin;
		//end往前走，不断更新
		--end;
	}
}

void ShellSort(int* a, int n)
{
	int gap = n;
	while (gap > 1)
	{
		gap = gap / 3 + 1;

		for (int i = 0; i < n - gap; i++)
		{
			int end = i;
			int tmp = a[end + gap];
			while (end >= 0)
			{
				if (tmp < a[end])
				{
					a[end + gap] = a[end];
					end -= gap;
				}
				else
				{
					break;
				}
			}
			a[end + gap] = tmp;
		}
	}
}

//void ShellSort(int* a, int n)
//{
//	int gap = n;
//	while (gap > 1)
//	{
//		gap = gap / 3 + 1;
//		for (int j = 0; j < gap; j++)
//		{
//			for (int i = j; i < n - gap; i += gap)
//			{
//				int end = i;
//				int tmp = a[end + gap];
//				while (end >= 0)
//				{
//					if (tmp < a[end])
//					{
//						a[end + gap] = a[end];
//						end -= gap;
//					}
//					else
//					{
//						break;
//					}
//					a[end + gap] = tmp;
//				}
//			}
//		}
//	}
//}
//void QuickSort(int* a, int begin, int end)
//{
//	if (begin >= end)
//		return;
//	int left = begin;
//	int right = end;
//	int key = begin;
//	while (left < right)
//	{
//		while (left < right && a[key] <= a[right])
//		{
//			--right;
//		}
//		while (left < right && a[key] >= a[left])
//		{
//			++left;
//		}
//		Swap(&a[left], &a[right]);
//	}
//	Swap(&a[key], &a[left]);
//	key = left;
//	QuickSort(a, begin, key - 1);
//	QuickSort(a, key + 1, end);
//}


//int PartSort2(int* a, int begin, int end)
//{
//	//int midi = GetMidi(a, begin, end);
//	//Swap(&a[midi], &a[begin]);
//	int keyi = a[begin];
//	int hole = begin;
//	while (begin < end)
//	{
//		//右边找小，填到左边的坑
//		while (begin < end && a[end] >= keyi)
//		{
//			--end;
//		}
//		a[hole] = a[end];
//		hole = end;
//		//左边找到，填到右边的坑
//		while (begin < end && a[begin] <= keyi)
//		{
//			++begin;
//		}
//		a[hole] = a[begin];
//		hole = begin;
//	}
//	a[hole] = keyi;
//	return keyi;
//}
//void QuickSortNonR(int* a, int begin, int end)
//{
//	ST s;
//	STInit(&s);
//	STPush(&s, end);
//	STPush(&s, begin);
//
//	while (!STEmpty(&s))
//	{
//		int left = STTop(&s);
//		STPop(&s);
//		int right = STTop(&s);
//		STPop(&s);
//
//		int keyi = PartSort3(a, left, right);
//		// [left, keyi-1] keyi [keyi+1, right]
//		if (left < keyi - 1)
//		{
//			STPush(&s, keyi - 1);
//			STPush(&s, left);
//		}
//
//		if (keyi + 1 < right)
//		{
//			STPush(&s, right);
//			STPush(&s, keyi + 1);
//		}
//	}
//	STDestroy(&s);
//}
//int PartSort3(int* a, int begin, int end)
//{
//	//int midi = GetMidi(a, begin, end);
//	//Swap(&a[begin], &a[midi]);
//	int prev = begin;
//	int cur = prev + 1;
//	int keyi = begin;
//	while (cur <= end)
//	{
//		if (a[cur] < a[keyi] && ++prev != cur)
//		{
//			Swap(&a[prev], &a[cur]);
//		}
//		++cur;
//	}
//	Swap(&a[keyi], &a[prev]);
//	keyi = prev;
//	return prev;
//}
//void QuickSort(int* a, int begin, int end)
//{
//	if (begin >= end)
//		return;
//
//	int keyi = PartSort3(a, begin, end);
//	QuickSort(a, begin, keyi - 1);
//	QuickSort(a, keyi + 1, end);
//}

void _MergeSort(int* a, int begin, int end, int* tmp)
{
	if (begin >= end)
		return;
	int mid = (begin + end) / 2;
	_MergeSort(a, begin, mid, tmp);
	_MergeSort(a, mid + 1, end, tmp);

	//[begin,mid] [mid+1,end]归并
	int begin1 = begin, end1 = mid;
	int begin2 = mid + 1, end2 = end;
	int i = begin;
	while (begin1 <= end1 && begin2 <= end2)
	{
		if (a[begin1] < a[begin2])
		{
			tmp[i++] = a[begin1++];
		}
		else
		{
			tmp[i++] = a[begin2++];
		}
	}
	while (begin1 <= end1)
	{
		tmp[i++] = a[begin1++];
	}
	while (begin2 <= end2)
	{
		tmp[i++] = a[begin2++];
	}
	memcpy(a + begin, tmp + begin, sizeof(int) * (end - begin+1));
}
//归并排序
void MergeSort(int* a, int n)
{
	int* tmp = (int*)malloc(sizeof(int) * n);
	if (tmp == NULL)
	{
		printf("malloc fail");
		return;
	}
	_MergeSort(a, 0, n - 1, tmp);

	free(tmp);
}